package com.eddie.search;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * @author Eddie
 */
public class FibonacciSearch {
    private static final int MAX_SIZE = 20;

    public static void main(String[] args) {
        int[] arr = {1, 8, 10, 89, 1000, 1234};
        int i = fibSearch(arr, 1234);
        System.out.println(i);

    }

    /**
     *     因为后面我们mid=low+F(k-1)-1,
     *     需要使用到斐波那契数列,
     *     因此我们需要先获取到一个斐波那契数列
     */
    public static int fib(int k){
        if(k==0||k==1){
            return 1;
        }else{
            return fib(k-1)+fib(k-2);
        }
    }

    /**
     * 斐波那契查找算法
     * 使用非递归的方式
     *
     * @param arr  数组
     * @param findVal 我们需要查找的关键码（值）
     * @return 返回对应下标，没有返回-1
     */
    public static int fibSearch(int[] arr, int findVal) {
        int low=0,high=arr.length-1;
        //用来表示斐波那契分割数值的下标
        int k =0;
        int mid;
        while (high>fib(k)-1){
            k++;
        }
        //因为f[k]值可能大于a的长度,因此我们需要使用Arrays类,
        // 构造一个新的数组,并指向temp[]，使用arr数组最后的数填充temp
        int[] temp = Arrays.copyOf(arr,fib(k));
        for (int i = high+1; i < temp.length; i++) {
            temp[i]=arr[high];
        }
        while (low<=high){
            mid = low+fib(k-1)-1;
            /*
            f[k] = f[k-1] + f[k-2]
            因为前面有f[k-1]个元素,所以可以继续拆分f[k-1] = f[k-2] + f[k-3]
            即在f[k-1]的前面继续查找k--
             */
            if(findVal<temp[mid]){
                high=mid-1;
                k--;
            }
            /*
            f[k] = f[k-1] + f[k-2]
            因为后面我们有f[k-2]，所以可以继续拆分f[k-2] = f[k-3] + f[k-4]
            即在f[k-2]的前面进行查找k-=2
             */
            else if(findVal>temp[mid]){
                low = mid+1;
                k-=2;
            }else{
                if(mid<=high){
                    return mid;
                }
                else{
                    return high;
                }
            }
        }
        return -1;
    }
}
